/* s2 - bit-twiddling magic within a word
   Copyright (C) 2018 Ariadne Devos

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

#ifndef _sHT_BITOPS_H
#define _sHT_BITOPS_H

#include <limits.h>
#include <stdint.h>
#include <endian.h>

#ifdef UINT64_MAX

/** If @var{word} was loaded from memory as-is, correct it as-if the
  architecture was big-endian. */
__attribute__((const))
static inline uint64_t
sHT_htobe64(uint64_t word)
{
	return htobe64(word);
}

/** Return the array as a register, even if it is unaligned.

  This may be an expensive operation, depending on the architecture
  and microarchitecture. */
__attribute__((const))
static inline uint64_t
sHT_unaligned_load64(const char bytes[8])
{
	uint64_t word;
	__builtin_memcpy(&word, bytes, 8);
	return word;
}

/** Count the number of leading zero bits.

  If word is zero, there are 8 leading zero bits.

  This may be an expensive operation, depending on the architecture
  and microarchitecture. */
__attribute__((const))
static inline int
sHT_clz64(uint64_t word)
{
#if UINT64_MAX == LLONG_MAX
	return __builtin_clzll(word);
#elif UINT64_MAX == LONG_MAX
	return __builtin_clzl(word);
#else
	return __builtin_clz(word);
#endif

}

/* See 'bitops/zero-index/any.c'. */
#if defined(sHT_word_byte_index64_benchmarking)
#elif defined(__aarch64__)
# define sHT_word_byte_index64_clz
#endif
#ifdef sHT_word_byte_index64_clz
# define sHT_word_zero_index_prepare(x) ((x) ^ ~UINT64_C(0))
#else
# define sHT_word_zero_index_prepare(x) (x)
#endif

/** Find the index of the first zero byte in an word

  @var{bytes}: when laid out in memory, an array of 8 bytes

  @var{bytes} must be massaged by @var{sHT_word_zero_index_prepare}
  first.

  If no byte is zero, return 8. The return value may speculatively
  be incorrect, but it is always within bounds. */
__attribute__((const))
int
sHT_word_zero_index64(uint64_t bytes);

/** Find the index of the first byte equal to @var{byte} in a word

  @var{bytes}: when laid out in memory, an array of 8 bytes

  If no byte is zero, return 8. The return value may speculatively
  be incorrect, but it is always within bounds. */
__attribute__((const))
static inline int
sHT_word_byte_index64(uint64_t bytes, uint8_t byte)
{
	/* xor out the character to reduce the problem to searching
	   for a zero byte. */
	bytes ^= byte * 0x0101010101010101;
	return sHT_word_zero_index64(sHT_word_zero_index_prepare(bytes));
}
#define sHT_word_byte_index64 sHT_word_byte_index64

#endif

#endif
